# 《对角线遍历》

# 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

# m*n矩阵对角线遍历
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        # 定义并初始化变量
        row = len(mat)     # 获取矩阵行数，用于判断纵坐标索引是否越界
        col = len(mat[0])  # 获取矩阵列数，用于判断横坐标索引是否越界
        x, y = 0, 0        # 初始化下标索引，横坐标x代表列，纵坐标y代表行
        mat_copy = []      # 存储每次遍历到的元素，最终结果作为函数返回值
        flag = True        # 标记遍历方向，右上方为True，左下方为False
        # 判断几种特殊情况：可省略
        # if row == 0:       # 矩阵为空
        #     return mat
        # elif row == 1:     # 矩阵只有一行
        #     return mat[0]
        # elif col == 1:     # 矩阵只有一列
        #     mat_copy = [mat[i][0] for i in range(row)]
        #     return mat_copy
        # 经上述代码筛选后，矩阵不止一行或一列
        # 因为索引从0开始，所以x,y不能等于col,row
        while x < col and y < row:
            # 将上一次循环获取到的x,y坐标用于mat_copy赋值
            mat_copy += [mat[y][x]]
            # 判断下一步索引是否越界，每次将越界时将flag置反，并根据越界情况修改x,y的值
            # 向右上方遍历时，先若右越界则向下遍历一格，后若上越界则向右遍历一格，并将flag置为False
            if flag == True:
                if x+1>=col:
                    y += 1
                    flag = False
                elif y-1<0:
                    x += 1
                    flag = False
                else:
                    x += 1
                    y -= 1
            # 向左下方遍历时，先若下越界则向右遍历一格，后若左越界则向下遍历一格，并将flag置为True
            else:
                if y+1>=row:
                    x += 1
                    flag = True
                elif x-1<0:
                    y += 1
                    flag = True
                else:
                    x -= 1
                    y += 1
        return mat_copy            



# 5*5矩阵各元素下标：
# 00 01 02 03 04
# 10 11 12 13 14
# 20 21 22 23 24
# 30 31 32 33 34
# 40 41 42 43 44

# 5*5矩阵按对角线遍历，各层元素下标：
# 1 00
# 2 01 10
# 3 20 11 02
# 4 03 12 21 30
# 5 40 31 22 13 04
# 6 14 23 32 41
# 7 42 33 24
# 8 34 43
# 9 44

# n*n矩阵对角线遍历
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        length = len(mat)
        mat_copy = []
        for i in range(1, length*2):
            items = length-abs(length-i)
            if i<=length:
                max = i-1
                min = 0
            else:
                max = length-1
                min = i-length
            if i%2 == 0:
                for j in range(items):
                    mat_copy += [mat[min][max]]
                    max = max-1
                    min = min+1
            else:
                for j in range(items):
                    mat_copy += [mat[max][min]]
                    max = max-1
                    min = min+1
        return mat_copy

            
# mat_copy = [mat[][] for j in range(items)]

# n*n矩阵各元素下标：
# 00 01 02 ............... 0(n-1)
# 10 11 12 ............... 1(n-1)
# 20 21 22 ............... 2(n-1)
# .. .. .. ............... ..
# (n-1)0 (n-1)1 (n-1)2 ... (n-1)(n-1)

# 当n为奇数时，各层元素下标：
# ...1: 00
# ...2: 01 10
# ...3: 20 11 02
# ....: .. .. ..
# ...n: (n-1)0 (n-2)1 ... 1(n-2) 0(n-1)
# .n+1: 1(n-1) 2(n-2) ... (n-2)2 (n-1)1
# ....: .. .. ..
# 2n-1: (n-1)(n-1)

# 当n为偶数时，各层元素下标：
# ...1: 00
# ...2: 01 10
# ...3: 20 11 02
# ....: .. .. .. ..
# ...n: 0(n-1) 1(n-2) ... (n-1)0 (n-2)1
# .n+1: (n-1)1 (n-2)2 ... 2(n-2) 1(n-1)
# ....: .. .. ..
# 2n-1: (n-1)(n-1)

# 由上可知：
# 1、任意n*n的矩阵按对角线遍历，共有layers=(n-1)*2+1=2n-1层
# 2、同层元素，（行列）索引和相等，且等于层数-1：row+col=i-1
# 3、元素个数与层数关系式：items=n-|n-i|
# 4、第i层第j个元素下标：mat[][]
# 奇、偶，

# 示例代码：
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        x, y = 0, 0
        n = len(mat) - 1
        m = len(mat[0]) - 1
        # 只有一行或者一列的处理
        if n == 0:
            return mat[0]
        elif m == 0:
            result = [num[0] for num in mat]
            return result
        # 普通情况
        result = []
        x_dign_move, y_dign_move = 0, 0
        switch = True
        while True:
            result.append(mat[x][y])

            # 直走方式
            # 左下顶点
            if x == 0 and y == m:
                x += 1
            # 右上顶点
            elif x == n and y == 0:
                y += 1
            # 边上
            else:
                if x == 0 or x == n:
                    y += 1
                elif y == 0 or y == m:
                    x += 1
            # 退场处理
            if x == n and y == m:
                result.append(mat[x][y])
                break

            # 设置对角线移动方式
            if switch:
                x_dign_move = 1
                y_dign_move = -1
                switch = False
            else:
                x_dign_move = -1
                y_dign_move = 1
                switch = True

            # 斜对角移动
            while True:
                result.append(mat[x][y])
                x += x_dign_move
                y += y_dign_move
                # 撞边就退出
                if (not switch and (y == 0 or x == n)) or (switch and (y == m or x == 0)):
                    break
        return result
